例题： 2017（简单）

题目链接

1

题目大意
给4个数a, b, c, d， 问有多少对(x, y) a <= x <= b， c <= y <= d 并且x * y % 2017 == 0 。

分析
因为2017是质数， 所以只需要 求 [a, b]中2017的个数 乘以 [c, d]中1的个数 加上 [c, d] 中2017 的个数 乘以 [a, b] 中1的个数， 减去 [a, b]中2017的个数 乘以 [c, d] 中2017 的个数(去重)。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

#define eps 1e-8
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
int main() {
    ios::sync_with_stdio(false);
    ll a, b, c, d;
    ll ans;
    while(cin >> a >> b >> c >> d){
        ans = 0;
        a--, c--;
        ans += (b / 2017 - a / 2017) * (d - c);
        ans += (d / 2017 - c / 2017) * (b - a);
        ans -= (b / 2017 - a / 2017) * (d / 2017 - c / 2017);
        cout << ans << "\n";
    }
    return 0;
}

例题： 2018（普通）

题目链接

1

题目大意
给4个数a, b, c, d， 问有多少对(x, y) a <= x <= b， c <= y <= d 并且x * y % 2018 == 0 。

分析
由于2018只有四个因数， 也是简单了不少。
所以 需要 求 [a, b]中2018的个数 乘以 [c, d]中1的个数 加上 [c, d] 中2018 的个数 乘以 [a, b] 中1的个数， 减去 [a, b]中2018的个数 乘以 [c, d] 中2018 的个数(去重)。
求 [a, b]中1009的个数 乘以 [c, d]中2的个数 加上 [c, d] 中1009 的个数 乘以 [a, b] 中2的个数， 不需要去重， 因为不可能有重复的。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

#define eps 1e-8
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
ll _(ll x){
    x /= 1009;
    if (x & 1)
        return x / 2 + 1;
    return x / 2;
}

int main() {
    ios::sync_with_stdio(false);
    ll a, b, c, d;
    ll ans;
    while(cin >> a >> b >> c >> d){
        ans = 0;
        a--, c--;
        ans += (b / 2018 - a / 2018) * (d - c);
        ans += (d / 2018 - c / 2018) * (b - a);
        ans += (_(b) - _(a)) * (d / 2 - c / 2 - d / 2018 + c / 2018);
        ans += (_(d) - _(c)) * (b / 2 - a / 2 - b / 2018 + a / 2018);
        ans -= (b / 2018 - a / 2018) * (d / 2018 - c / 2018);
        cout << ans << "\n";
    }


    return 0;
}

例题： 2016（困难）

题目链接
1

题目大意

给2个数n, m， 问有多少对(x, y) 1 <= x <= n， 1 <= y <= m 并且x * y % 2016 == 0 。

分析
2016有36个因子， 再用这种方法就有点难受咯。
讲讲比较正的解法。
任何一个数a 都可以表示为 a = a / 2016 * 2016 + a % 2016 所以只要求 (x % 2016 * y % 2016) % 2016 == 0 对于(x, y ) 有多少对。
具体看AC代码

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstdio>

typedef long long ll;

using namespace std;
ll n, m;
int num1[2020], num2[2020];

int main() {
    while (scanf("%lld%lld", &n, &m) != EOF) {
        // num1[i] n % 2016 == i 的个数
        // num2[i] m % 2016 == i 的个数
        for (int i = 0; i <= 2015; i++) num1[i] = n / 2016, num2[i] = m / 2016;
        for (int i = 1; i <= 2015; i++) {
            if (i <= n % 2016) num1[i]++;
            if (i <= m % 2016) num2[i]++;
        }
        ll ans = 0;
        for (int i = 0; i <= 2015; i++) {
            for (int j = 0; j <= 2015; j++) {
                if (i * j % 2016 == 0) {
                    ans += num1[i] * num2[j];
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan